package 贪心算法._435_无重叠区间;

import java.util.Arrays;
import java.util.Comparator;

/** 435
 * 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
 *
 * 注意:
 *      可以认为区间的终点总是大于它的起点。
 *      区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/non-overlapping-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    //贪心算法
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length==0){
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1]-interval2[1];
            }
        });
//        for(int[] a:intervals){
//            for (int i:a){
//                System.out.print(i+" ");
//            }
//            System.out.println();
//        }
        int n=intervals.length;
        int right=intervals[0][1];
        int ans=1;
        for(int i=1;i<n;i++){
            if(intervals[i][0]>=right){
                ans++;
                right=intervals[i][1];
            }
        }
        return n-ans;
    }

    public static void main(String[] args) {

        System.out.println(new Solution().eraseOverlapIntervals(new int[][]{{1,2},{2,4},{1,3}}));
    }
}
